package sword_offer;

import java.lang.reflect.AnnotatedArrayType;

/**
 * @ClassName _16myPow
 * @Description: 实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：x = 2.00000, n = 10
 * 输出：1024.00000
 * 示例 2：
 *
 * 输入：x = 2.10000, n = 3
 * 输出：9.26100
 * 示例 3：
 *
 * 输入：x = 2.00000, n = -2
 * 输出：0.25000
 * 解释：2-2 = 1/22 = 1/4 = 0.25
 *  
 *
 * 提示：
 *
 * -100.0 < x < 100.0
 * -231 <= n <= 231-1
 * -104 <= xn <= 104
 *  
 *
 * 注意：本题与主站 50 题相同：https://leetcode-cn.com/problems/powx-n/
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/shu-zhi-de-zheng-shu-ci-fang-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Author: yongliang.ma
 * @Create_time:2022/10/13 11:03
 */
public class _16myPow {

    // 空间复杂度O(n)、时间复杂度O(log n)
    public double myPow(double x, int n) {
        long N = n;// 由于n范围为Integer.MIN_VALUE，取反之后可能会溢出 所以使用long类型来接收

        double res = cur(x, Math.abs(N));
        if (n >= 0){
            return res;
        }else {
            return 1/res;
        }
    }
    // 考虑大于0的情况
    public double cur(double x, long n){
        if (n == 0)
            return 1;
        if (n % 2 == 0){
            double res = cur(x, n/2);
            return res * res;
        }else {
            double res = cur(x, n/2);
            return res * res * x;
        }
    }


    // 递归改为迭代，二进制的表示法 联想10表示为二进制为1010，
    public double loop(double x, long n){
        double res = 1, x_con = x;
        while (n > 0){
            if (n % 2 == 1){
                res = res * x_con;
            }
            x_con = x_con * x_con;
            n = n >>> 1;
        }
        return res;
    }
}
